A system for reducing the amount of jaggedness (anti-aliasing) of the edges of text or synthetic graphics that are angularly close to the horizontal (fast scan direction) by using the different run boundaries in a run length encoding of the compressed text or graphic to generate edge pixels that are intermediate shades of gray.
Text or graphical data is normally transmitted or stored in a Page Description Language (such as Adobe's PostScript) using a mathematical representation that is not correlated to the characteristics of a particular output device such as a raster display or laser printer. To actually display or print the text or graphical data, it must be converted to rasters suitable for the output device. The resolution of the display or printer will then have a fixed number of picture elements ("pixels") per square inch, see FIG. 1. Because the output device has a fixed resolution, the mathematically defined ideal shape 10 of the text or graphic must be approximated, 11. When the edge of the text or graphic's definition does not call for it to be exactly straight and aligned either vertically or horizontally with the output rasters, a stair stepped, or jagged edge will result. If the output device's resolution is low, these "jaggies" will be visible and objectionable. This situation, showing both the ideal shape and the approximation made by rasterizing at a particular resolution, is illustrated in FIG. 1.
Increasing the resolution in both direction increases the cost of the apparatus, sometimes by order O(n.sup.2). One approach in the prior art is to increase the resolution only in the fast-scan direction, see FIG. 2. Sometimes called "high-addressability," this approach takes advantage of the fact that in many cases, the rasterization process converts the mathematical shape 12 first to a run-length encoded form before producing discrete pixels 13. Thus increasing the resolution in the fast scan direction amounts to increasing the accuracy ("addressability") of the run lengths. But to be of value, the final output device must support the additional resolution, and this is often still costly. This situation is shown in FIG. 2. Notice that the "jaggies" are reduced, though still visible, at the left and right, but not the top and bottom of the circle.
An alternate approach to decreasing the size of the "jaggies" by increasing the resolution is to reduce their visibility, see FIG. 3. One way to do this is to calculate by some means the fractional portion of each edge pixel that would be inside the ideal mathematical shape 14, and set the color of that pixel to a blend composed of the color of the text or graphic and the color of the background adjacent to the edge. The output device must be able to render gray intermediate tones by some means for this method to be effective.
A number of approaches in the prior art have been taken to make the calculation of the intermediate gray tone. One is to actually produce pixels at a higher integer multiple of the output device's resolution, and treat them as sub-pixels of the device's pixels. The needed blend value can then be calculated by comparing the number of high resolution sub-pixels inside the mathematical edge and with the number outside. The approach saves the cost of increased resolution in the output apparatus, but incurs all the cost in processing time and memory associated with the rasterization process. This approach is illustrated in FIG. 3.
One commercial example of this approach is a printing system that rasterizes at increased resolution (1600.times.1600 rather than the nominal 400.times.400) and then averages the resulting 16 pixels to produce pixels at 400.times.400, but with gray values at the edges. The time to do this is significant, especially the time spent producing the extra scanlines.
In the fast-scan direction, the increased time to produce the higher resolution is minimal if run-length encoding is used, as described previously. This run-length-based fast-scan anti-aliasing is effective in reducing the visibility of "jaggies" nearly perpendicular in angle (greater than 45 degrees) to the fast-scan direction. The processing time and apparatus cost can be further controlled if inherently sampled image data, as distinct from synthetic graphics or text, are treated separately and not converted to the higher resolution. This subject is treated in U.S. Pat. No. RE35657, which is hereby incorporated herein, and its references. However, a method is needed to reduce the visibility of "jaggies" within 45 degrees in angle to the fast-scan direction.